package leetcode.Hot100;

/**
 * @author Cheng Jun
 * @version 1.0
 * @Description: 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 * 0 <= nums.length <= 10^5
 * -10^9 <= nums[i] <= 10^9
 * nums 是一个非递减数组
 * -10^9 <= target <= 10^9
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/12/9 17:26
 * 二刷 面试题
 * 题解：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/tu-jie-er-fen-zui-qing-xi-yi-dong-de-jia-ddvc/
 */
public class searchRange {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        int[] resArr = searchRange1(nums, 1);
        System.out.println(resArr[0]);
        System.out.println(resArr[1]);
    }

    // 暴力解法: 时间复杂度是O(n)
    static int[] searchRange(int[] nums, int target) {
        int start = -1;
        int end = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > target) {
                break;
            }
            if (nums[i] == target) {
                if (start == -1) {
                    start = i;
                }
                end = i;
            }
        }
        int[] res = new int[]{start, end};
        return res;
    }

    // 二分查找，查找元素的起点和终点
    // 编程时，尽量优先使用 a < b, a <= b ，而不要使用 b > a, 因为二分查找的数组是有序的，小于号更有利于想象target的位置分布
    static int[] searchRange1(int[] nums, int target) {
        // 1, 1, 1, 1, 1
        int[] resArr = {-1, -1};
        if(nums.length == 0) return resArr;
        int leftIndex = searchLeft(nums, target);
        // 如果左边界为 -1 表示不存在target
        if (leftIndex == -1) {
            return resArr;
        } else {
            resArr[0] = leftIndex;
        }
        int rightIndex = searchRight(nums, target);
        resArr[1] = rightIndex;
        return resArr;
    }

    /**
     * 搜索右边界：最后大于等于 target的元素位置
     *
     * @param nums
     * @param target
     * @return int
     * @author Cheng Jun
     * @date 2022/7/16 15:10
     */
    private static int searchRight(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 区间划分 [left, mid -1], [mid, right]
            int mid = (left + right + 1) / 2;
            if (nums[mid] <= target) {
                // 去mid右边找最后大于等于target的位置
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return nums[right] == target ? right : -1;
    }

    /**
     * 搜索左边界：首个大于等于 target的元素位置
     *
     * @param nums
     * @param target
     * @return int
     * @author Cheng Jun
     * @date 2022/7/16 15:02
     */
    private static int searchLeft(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            // 区间划分 [left, mid], [mid+1, right]
            int mid = (left + right) / 2;
            if (target <= nums[mid]) {
                // 去mid左边找首个大于等于target元素的位置
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 搜索空间压缩到最后，首个大于等于 target的元素位置
        return nums[right] == target ? right : -1;
    }
}
